#include "stdio.h"
#include "stdlib.h"
#include "LinkQueue.h"

void init(BiTNode *T);
void insert(BiTNode *T,ElemType e);
void visit(BiTNode *T);
void threadVisit(BiTNode *T);
void postOrder(BiTree T);
void preOrder(BiTree T);
void inOrder(BiTree T);
void sequenceTraversal(BiTree T);
void inThread(BiTree T);
void preThread(BiTree T);
void postThread(BiTree T);

//find inorder node's next node
ThreadNode *firstNode(ThreadNode *p);
ThreadNode *nextNode(ThreadNode *p);


//BiTNode *p; //want to find node
//BiTNode *pre = NULL;//storage pre node
//BiTNode *final = NULL;//storage the node you want to find

ThreadNode *pre=NULL;

int main(){
	return 0;
}

void init(BiTNode *T){
	T = (BiTree)malloc(sizeof(BiTNode));
	T->data = {1};
	T->lchild = NULL;
	T->rchild = NULL;
}

void insert(BiTNode *T,char e){
	BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
	p->data = e;
	p->lchild = NULL;
	p->rchild = NULL;
	T->lchild = p;
}
void visit(BiTNode *T){
	if(T!=NULL)
		printf("%c ",T->data);
	
//	if (q==p)
//		final = pre;
//	else 
//		pre = q;
	
}

void postOrder(BiTree T){
	while(T!= NULL){
		postOrder(T->lchild);
		postOrder(T->rchild);
		visit(T);
	}
}
void preOrder(BiTree T){
	while(T!= NULL){
		visit(T);		
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}
void inOrder(BiTree T){
	while(T!= NULL){
		inOrder(T->lchild);
		visit(T);
		inOrder(T->rchild);
	}
}
void inThread(BiTree T){
	while(T!= NULL){
		postOrder(T->lchild);
		threadVisit(T);
		postOrder(T->rchild);
	}
}

void sequenceTraversal(BiTree T){
	LinkQueue Q;
	init(Q);
	BiTree p;
	enQueue(Q,T);
	while(!isEmpty(Q)){
		deQueue(Q,p);
		visit(p);
		if(p->lchild!=NULL)
			enQueue(Q,p->lchild);
		if(p->rchild!=NULL)
			enQueue(Q,p->rchild);
	}
}

void inThread(BiTree T){
	while(T!= NULL){
		inThread(T->lchild);
		threadVisit(T);
		inThread(T->rchild);
	}
}
//the finally:if(pre->rchild==NULL) pre->rtag=1;

void preThread(BiTree T){
	while(T!= NULL){
		threadVisit(T);
		if(T->flagl==0)
			preThread(T->lchild);
		preThread(T->rchild);
	}
}
//the finally:if(pre->rchild==NULL) pre->rtag=1;

void postThread(BiTree T){
	while(T!= NULL){
		postThread(T->lchild);
		postThread(T->rchild);
		threadVisit(T);	
	}
}
//the finally:if(pre->rchild==NULL) pre->rtag=1;

void threadVisit(BiTNode *T){
	if(T->lchild==NULL){
		T->lchild = pre;
		T->flagl = 1;
	}
	if(pre != NULL && pre->rchild == NULL){
		pre->rchild = T;
		pre->flagr = 1;
	}
	pre = T;
	printf("%c ",T->data);
}

ThreadNode *firstNode(ThreadNode *p){
	while(p->flagl==0) p=p->lchild;
	return p;	
}
ThreadNode *nextNode(ThreadNode *p){
	if(p->flagr==0) return firstNode(p->rchild);
	else return p->rchild;	
}















